{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #String Compression"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #two-pointers #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #双指针 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: compress"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #压缩字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符数组 <code>chars</code> ，请使用下述算法压缩：</p>\n",
    "\n",
    "<p>从一个空字符串 <code>s</code> 开始。对于 <code>chars</code> 中的每组 <strong>连续重复字符</strong> ：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果这一组长度为 <code>1</code> ，则将字符追加到 <code>s</code> 中。</li>\n",
    "\t<li>否则，需要向 <code>s</code> 追加字符，后跟这一组的长度。</li>\n",
    "</ul>\n",
    "\n",
    "<p>压缩后得到的字符串 <code>s</code> <strong>不应该直接返回</strong> ，需要转储到字符数组 <code>chars</code> 中。需要注意的是，如果组长度为 <code>10</code> 或 <code>10</code> 以上，则在 <code>chars</code> 数组中会被拆分为多个字符。</p>\n",
    "\n",
    "<p>请在 <strong>修改完输入数组后</strong> ，返回该数组的新长度。</p>\n",
    "\n",
    "<p>你必须设计并实现一个只使用常量额外空间的算法来解决此问题。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>chars = [\"a\",\"a\",\"b\",\"b\",\"c\",\"c\",\"c\"]\n",
    "<strong>输出：</strong>返回 6 ，输入数组的前 6 个字符应该是：[\"a\",\"2\",\"b\",\"2\",\"c\",\"3\"]\n",
    "<strong>解释：</strong>\"aa\" 被 \"a2\" 替代。\"bb\" 被 \"b2\" 替代。\"ccc\" 被 \"c3\" 替代。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>chars = [\"a\"]\n",
    "<strong>输出：</strong>返回 1 ，输入数组的前 1 个字符应该是：[\"a\"]\n",
    "<strong>解释：</strong>唯一的组是“a”，它保持未压缩，因为它是一个字符。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>chars = [\"a\",\"b\",\"b\",\"b\",\"b\",\"b\",\"b\",\"b\",\"b\",\"b\",\"b\",\"b\",\"b\"]\n",
    "<strong>输出：</strong>返回 4 ，输入数组的前 4 个字符应该是：[\"a\",\"b\",\"1\",\"2\"]。\n",
    "<strong>解释：</strong>由于字符 \"a\" 不重复，所以不会被压缩。\"bbbbbbbbbbbb\" 被 “b12” 替代。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= chars.length &lt;= 2000</code></li>\n",
    "\t<li><code>chars[i]</code> 可以是小写英文字母、大写英文字母、数字或符号</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [string-compression](https://leetcode.cn/problems/string-compression/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [string-compression](https://leetcode.cn/problems/string-compression/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"a\",\"a\",\"b\",\"b\",\"c\",\"c\",\"c\"]', '[\"a\"]', '[\"a\",\"b\",\"b\",\"b\",\"b\",\"b\",\"b\",\"b\",\"b\",\"b\",\"b\",\"b\",\"b\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# LCA query: return max weight\n",
    "def _lca(self, u: int, v: int) -> int:\n",
    "    if self.dep[u] > self.dep[v]:\n",
    "        u, v = v, u\n",
    "    # step 1: align to the same height\n",
    "    tmp = self.dep[v] - self.dep[u]\n",
    "    res = 0 # maximum weight in path\n",
    "    i = 0\n",
    "    while tmp:\n",
    "        if tmp & 1:\n",
    "            res = max(res, self.mw[v][i])\n",
    "            v = self.pa[v][i]\n",
    "        tmp >>= 1\n",
    "        i += 1\n",
    "    if u == v:\n",
    "        return res\n",
    "    # step 2: skip to lca\n",
    "    for i in range(14, -1, -1):\n",
    "        if (self.pa[v][i] != self.pa[u][i]):\n",
    "            res = max(res, self.mw[u][i], self.mw[v][i])\n",
    "            v = self.pa[v][i]\n",
    "            u = self.pa[u][i]\n",
    "    res = max(res, self.mw[u][0], self.mw[v][0])\n",
    "    return res\n",
    "class DSU:\n",
    "    \n",
    "    def __init__(self, n):\n",
    "        self.count = [1] * n \n",
    "        self.parent = [_ for _ in range(n)]\n",
    "\n",
    "    def find(self, i): # find root(i) and compress the path\n",
    "        if self.parent[i] != i:\n",
    "            self.parent[i] = self.find(self.parent[i])\n",
    "        return self.parent[i]\n",
    "\n",
    "    def union(self, i, j): # return if already connected\n",
    "        pi, pj = self.find(i), self.find(j)\n",
    "        if pi != pj:\n",
    "            if self.count[pi] < self.count[pj]:\n",
    "                pi, pj = pj, pi\n",
    "            self.parent[pj] = pi\n",
    "            self.count[pi] += self.count[pj]\n",
    "            return False\n",
    "        return True\n",
    "    \n",
    "class DistanceLimitedPathsExist:\n",
    "\n",
    "    def __init__(self, n: int, edgeList: List[List[int]]):\n",
    "        self.n = n\n",
    "        self.dsu = DSU(n)\n",
    "        self.edges = sorted(edgeList, key = lambda x: x[2]) # original edges\n",
    "        self.medges = [dict() for _ in range(n)] # edges in mst\n",
    "        self.pa = [[-1] * 15 for _ in range(n)] # 2 ** k-th parent in mst\n",
    "        self.mw = [[0] * 15 for _ in range(n)] # maximum weight to 2 ** k-th parent\n",
    "        self.dep = [0] * n # depth of nodes in mst\n",
    "        self._vis = [False] * n\n",
    "        # kruskal\n",
    "        self._kruskal()\n",
    "        # dfs\n",
    "        for i in range(n):\n",
    "            if self._vis[i] is False:\n",
    "                self.dep[i] = 1\n",
    "                self._dfs(i)\n",
    "                self.pa[i][0] = i\n",
    "        # init LCA\n",
    "        for i in range(1, 15):\n",
    "            for u in range(n):\n",
    "                self.pa[u][i] = self.pa[self.pa[u][i-1]][i-1]\n",
    "                self.mw[u][i] = max(self.mw[u][i-1], self.mw[self.pa[u][i-1]][i-1])\n",
    "        # debug\n",
    "        # print(self.medges)\n",
    "        # print(self.pa)\n",
    "        # print(self.mw)\n",
    "    \n",
    "    def _dfs(self, u):\n",
    "        self._vis[u] = True\n",
    "        for v, w in self.medges[u].items():\n",
    "            if self._vis[v]:\n",
    "                continue\n",
    "            self.dep[v] = self.dep[u] + 1\n",
    "            self.pa[v][0] = u\n",
    "            self.mw[v][0] = w\n",
    "            self._dfs(v)\n",
    "            \n",
    "    \n",
    "    def _kruskal(self):\n",
    "        for u, v, w in self.edges:\n",
    "            if self.dsu.union(u, v) is False: # edge in mst\n",
    "                self.medges[u][v] = w\n",
    "                self.medges[v][u] = w\n",
    "        \n",
    "    \n",
    "    # LCA query: return max weight\n",
    "    def _lca(self, u: int, v: int) -> int:\n",
    "        if self.dep[u] > self.dep[v]:\n",
    "            u, v = v, u\n",
    "        # align to the same height\n",
    "        tmp = self.dep[v] - self.dep[u]\n",
    "        res = 0 # maximum weight in path\n",
    "        i = 0\n",
    "        while tmp:\n",
    "            if tmp & 1:\n",
    "                res = max(res, self.mw[v][i])\n",
    "                v = self.pa[v][i]\n",
    "            tmp >>= 1\n",
    "            i += 1\n",
    "        if u == v:\n",
    "            return res\n",
    "        # skip to lca\n",
    "        for i in range(14, -1, -1):\n",
    "            if (self.pa[v][i] != self.pa[u][i]):\n",
    "                res = max(res, self.mw[u][i], self.mw[v][i])\n",
    "                v = self.pa[v][i]\n",
    "                u = self.pa[u][i]\n",
    "        res = max(res, self.mw[u][0], self.mw[v][0])\n",
    "        return res\n",
    "    \n",
    "    def query(self, p: int, q: int, limit: int) -> bool:\n",
    "        if self.dsu.find(p) != self.dsu.find(q): # not connected\n",
    "            return False\n",
    "        return self._lca(p, q) < limit\n",
    "\n",
    "\n",
    "\n",
    "# Your DistanceLimitedPathsExist object will be instantiated and called as such:\n",
    "# obj = DistanceLimitedPathsExist(n, edgeList)\n",
    "# param_1 = obj.query(p,q,limit)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distanceLimitedPathsExist(self, n: int, edgeList: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        ans = [False] * len(queries)\n",
    "        edgeList.sort(key=lambda x: x[2])\n",
    "        queries = sorted(enumerate(queries), key=lambda x: x[1][2])\n",
    "\n",
    "        UF = UnionFind(n)\n",
    "        j = 0\n",
    "        m = len(edgeList)\n",
    "        for i, (u, v, limit) in queries:\n",
    "            while j < m and edgeList[j][2] < limit:\n",
    "                UF.unionSet(edgeList[j][0], edgeList[j][1])\n",
    "                j += 1\n",
    "            ans[i] = UF.isSameSet(u, v)\n",
    "        \n",
    "        return ans \n",
    "\n",
    "        \n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int, m: int=None) -> None:\n",
    "        \"\"\"\n",
    "        build m disjoint sets from n nodes\n",
    "        T: O(N)\n",
    "        \"\"\"\n",
    "        self.parents = list(range(n))   \n",
    "        self.ranks = [0] * n            \n",
    "    \n",
    "    def findSet(self, i: int) -> int:\n",
    "        \"\"\"return root of node i's set\n",
    "           T: amortized O(α(N))  effectively O(1)\n",
    "             first O(N) then O(1)\n",
    "           path-compression  \n",
    "           Recursion\n",
    "        \"\"\"\n",
    "        if self.parents[i] == i:\n",
    "            return i\n",
    "        else:\n",
    "            self.parents[i] = self.findSet(self.parents[i])\n",
    "            return self.parents[i]\n",
    "        \n",
    "\n",
    "    \n",
    "    def unionSet(self, i: int, j: int) -> None:\n",
    "        \"\"\"若节点i和节点j来自2个不同的互斥集合，将两个集合合并 \n",
    "           union by rank   矮树作为高树的子树\n",
    "           T: amortized O(α(N))  effectively O(1)\n",
    "             first O(N) then O(1)\n",
    "        \"\"\"\n",
    "        ip, jp = self.findSet(i), self.findSet(j)\n",
    "\n",
    "        # 若两个节点来自同一互斥集合，返回\n",
    "        if ip == jp:\n",
    "            return \n",
    "\n",
    "        # 若A树矮，B树高，A树连到B树的根节点上，新树rank不变\n",
    "        if self.ranks[ip] < self.ranks[jp]:\n",
    "            self.parents[ip] = jp\n",
    "\n",
    "        # 若B树矮，A树高，B树连到A树的根节点上，新树rank不变\n",
    "        elif self.ranks[jp] < self.ranks[ip]:\n",
    "            self.parents[jp] = ip\n",
    "\n",
    "        # 若两树等高，任选一种方案，新树 rank +1\n",
    "        else:\n",
    "            self.parents[jp] = ip\n",
    "            self.ranks[ip] += 1\n",
    "    \n",
    "    def isSameSet(self, i: int, j: int) -> bool:\n",
    "        \"\"\"判断节点i和节点j是否属于同一集合\n",
    "           T: O(α(N) first O(N) then O(1)\n",
    "        \"\"\"\n",
    "        # path compression twice\n",
    "        return self.findSet(i) == self.findSet(j)\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:\n",
    "        # 1. build union find disjoint set without vertices in the initial array\n",
    "        n = len(graph)\n",
    "        initial = set(initial)\n",
    "        UF = UnionFind(n)\n",
    "\n",
    "        for i in range(n):\n",
    "            if i not in initial:\n",
    "                for j in range(n):\n",
    "                    if (j not in initial) and graph[i][j]:\n",
    "                        UF.unionSet(i, j)\n",
    "        \n",
    "        # 2. find root of each vertex in the initial array\n",
    "        hashmap = dict()\n",
    "        for i in initial:\n",
    "            roots = set([UF.findSet(j) for j in range(n) if (j not in initial) and graph[i][j]])\n",
    "            hashmap[i] = roots \n",
    "        \n",
    "        rootCounter = collections.Counter(itertools.chain(*hashmap.values()))\n",
    "\n",
    "\n",
    "        # 3. compare max reduced number of infected of each vertex in the initial array\n",
    "        initial = sorted(list(initial))\n",
    "        ans = initial[0]\n",
    "        maxSize = -1\n",
    "        for i in initial:\n",
    "            size = sum([UF.sizeSets[root] for root in hashmap[i] if rootCounter[root] == 1])\n",
    "            if size > maxSize:\n",
    "                ans = i \n",
    "                maxSize = size \n",
    "        return ans \n",
    "\n",
    "\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int, m: int=None) -> None:\n",
    "        \"\"\"\n",
    "        build m disjoint sets from n nodes\n",
    "        T: O(N)\n",
    "        \"\"\"\n",
    "        self.parents = list(range(n))  \n",
    "        self.ranks = [0] * n            \n",
    "        self.sizeSets = [1] * n         # sizeSets[i]: size of disjoint set rooted at vertex i\n",
    "\n",
    "    \n",
    "    def findSet(self, i: int) -> int:\n",
    "        \"\"\"return root of node i's set\n",
    "           T: amortized O(α(N))  effectively O(1)\n",
    "             first O(N) then O(1)\n",
    "           path-compression  \n",
    "           Recursion\n",
    "        \"\"\"\n",
    "        if self.parents[i] == i:\n",
    "            return i\n",
    "        else:\n",
    "            self.parents[i] = self.findSet(self.parents[i])\n",
    "            return self.parents[i]\n",
    "        \n",
    "\n",
    "    \n",
    "    def unionSet(self, i: int, j: int) -> None:\n",
    "        \"\"\"若节点i和节点j来自2个不同的互斥集合，将两个集合合并 \n",
    "           union by rank   矮树作为高树的子树\n",
    "           T: amortized O(α(N))  effectively O(1)\n",
    "             first O(N) then O(1)\n",
    "        \"\"\"\n",
    "        ip, jp = self.findSet(i), self.findSet(j)\n",
    "\n",
    "        # 若两个节点来自同一互斥集合，返回\n",
    "        if ip == jp:\n",
    "            return \n",
    "\n",
    "        # 若A树矮，B树高，A树连到B树的根节点上，新树rank不变\n",
    "        if self.ranks[ip] < self.ranks[jp]:\n",
    "            self.parents[ip] = jp\n",
    "            self.sizeSets[jp] += self.sizeSets[ip]\n",
    "\n",
    "        # 若B树矮，A树高，B树连到A树的根节点上，新树rank不变\n",
    "        elif self.ranks[jp] < self.ranks[ip]:\n",
    "            self.parents[jp] = ip\n",
    "            self.sizeSets[ip] += self.sizeSets[jp]\n",
    "\n",
    "        # 若两树等高，任选一种方案，新树 rank +1\n",
    "        else:\n",
    "            self.parents[jp] = ip\n",
    "            self.sizeSets[ip] += self.sizeSets[jp]\n",
    "            self.ranks[ip] += 1\n",
    "\n",
    "    \n",
    "    def isSameSet(self, i: int, j: int) -> bool:\n",
    "        \"\"\"判断节点i和节点j是否属于同一集合\n",
    "           T: O(α(N) first O(N) then O(1)\n",
    "        \"\"\"\n",
    "        # path compression twice\n",
    "        return self.findSet(i) == self.findSet(j)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:\n",
    "        n = len(graph)\n",
    "        UF = UnionFind(n)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i < j and graph[i][j]:\n",
    "                    UF.unionSet(i, j)\n",
    "        \n",
    "        hashmap = collections.Counter([UF.findSet(i) for i in initial])\n",
    "        \n",
    "        initial.sort()\n",
    "        maxsize = 0\n",
    "        ans = initial[0] \n",
    "        for i in initial:\n",
    "            root = UF.findSet(i)\n",
    "            if hashmap[root] == 1:\n",
    "                size = UF.sizeSets[root]\n",
    "            else:\n",
    "                size = 0\n",
    "            if size > maxsize:\n",
    "                ans = i \n",
    "                maxsize = size \n",
    "\n",
    "        return ans \n",
    "\n",
    "\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int, m: int=None) -> None:\n",
    "        \"\"\"\n",
    "        build m disjoint sets from n nodes\n",
    "        T: O(N)\n",
    "        \"\"\"\n",
    "        self.parents = list(range(n))  \n",
    "        self.ranks = [0] * n            \n",
    "        self.sizeSets = [1] * n         # sizeSets[i]: size of disjoint set rooted at vertex i\n",
    "\n",
    "    \n",
    "    def findSet(self, i: int) -> int:\n",
    "        \"\"\"return root of node i's set\n",
    "           T: amortized O(α(N))  effectively O(1)\n",
    "             first O(N) then O(1)\n",
    "           path-compression  \n",
    "           Recursion\n",
    "        \"\"\"\n",
    "        if self.parents[i] == i:\n",
    "            return i\n",
    "        else:\n",
    "            self.parents[i] = self.findSet(self.parents[i])\n",
    "            return self.parents[i]\n",
    "        \n",
    "\n",
    "    \n",
    "    def unionSet(self, i: int, j: int) -> None:\n",
    "        \"\"\"若节点i和节点j来自2个不同的互斥集合，将两个集合合并 \n",
    "           union by rank   矮树作为高树的子树\n",
    "           T: amortized O(α(N))  effectively O(1)\n",
    "             first O(N) then O(1)\n",
    "        \"\"\"\n",
    "        ip, jp = self.findSet(i), self.findSet(j)\n",
    "\n",
    "        # 若两个节点来自同一互斥集合，返回\n",
    "        if ip == jp:\n",
    "            return \n",
    "\n",
    "        # 若A树矮，B树高，A树连到B树的根节点上，新树rank不变\n",
    "        if self.ranks[ip] < self.ranks[jp]:\n",
    "            self.parents[ip] = jp\n",
    "            self.sizeSets[jp] += self.sizeSets[ip]\n",
    "\n",
    "        # 若B树矮，A树高，B树连到A树的根节点上，新树rank不变\n",
    "        elif self.ranks[jp] < self.ranks[ip]:\n",
    "            self.parents[jp] = ip\n",
    "            self.sizeSets[ip] += self.sizeSets[jp]\n",
    "\n",
    "        # 若两树等高，任选一种方案，新树 rank +1\n",
    "        else:\n",
    "            self.parents[jp] = ip\n",
    "            self.sizeSets[ip] += self.sizeSets[jp]\n",
    "            self.ranks[ip] += 1\n",
    "\n",
    "    \n",
    "    def isSameSet(self, i: int, j: int) -> bool:\n",
    "        \"\"\"判断节点i和节点j是否属于同一集合\n",
    "           T: O(α(N) first O(N) then O(1)\n",
    "        \"\"\"\n",
    "        # path compression twice\n",
    "        return self.findSet(i) == self.findSet(j)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:\n",
    "        n = len(graph)\n",
    "        UF = UnionFind(n)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i < j and graph[i][j]:\n",
    "                    UF.unionSet(i, j)\n",
    "        \n",
    "        hashmap = collections.Counter([UF.findSet(i) for i in initial])\n",
    "        initial.sort()\n",
    "        ans = initial[0] \n",
    "        maxsize = 0\n",
    "        for i in initial:\n",
    "            root = UF.findSet(i)\n",
    "            # if a connected component has > 1 initials, remove one initial still infect the whole component\n",
    "            if hashmap[root] == 1:\n",
    "                size = UF.sizeSets[root]\n",
    "                if size > maxsize:\n",
    "                    ans = i \n",
    "                    maxsize = size \n",
    "\n",
    "        return ans \n",
    "\n",
    "\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int, m: int=None) -> None:\n",
    "        \"\"\"\n",
    "        build m disjoint sets from n nodes\n",
    "        T: O(N)\n",
    "        \"\"\"\n",
    "        self.parents = list(range(n))  \n",
    "        self.ranks = [0] * n            \n",
    "        self.sizeSets = [1] * n         # sizeSets[i]: size of disjoint set rooted at vertex i\n",
    "\n",
    "    \n",
    "    def findSet(self, i: int) -> int:\n",
    "        \"\"\"return root of node i's set\n",
    "           T: amortized O(α(N))  effectively O(1)\n",
    "             first O(N) then O(1)\n",
    "           path-compression  \n",
    "           Recursion\n",
    "        \"\"\"\n",
    "        if self.parents[i] == i:\n",
    "            return i\n",
    "        else:\n",
    "            self.parents[i] = self.findSet(self.parents[i])\n",
    "            return self.parents[i]\n",
    "        \n",
    "\n",
    "    \n",
    "    def unionSet(self, i: int, j: int) -> None:\n",
    "        \"\"\"若节点i和节点j来自2个不同的互斥集合，将两个集合合并 \n",
    "           union by rank   矮树作为高树的子树\n",
    "           T: amortized O(α(N))  effectively O(1)\n",
    "             first O(N) then O(1)\n",
    "        \"\"\"\n",
    "        ip, jp = self.findSet(i), self.findSet(j)\n",
    "\n",
    "        # 若两个节点来自同一互斥集合，返回\n",
    "        if ip == jp:\n",
    "            return \n",
    "\n",
    "        # 若A树矮，B树高，A树连到B树的根节点上，新树rank不变\n",
    "        if self.ranks[ip] < self.ranks[jp]:\n",
    "            self.parents[ip] = jp\n",
    "            self.sizeSets[jp] += self.sizeSets[ip]\n",
    "\n",
    "        # 若B树矮，A树高，B树连到A树的根节点上，新树rank不变\n",
    "        elif self.ranks[jp] < self.ranks[ip]:\n",
    "            self.parents[jp] = ip\n",
    "            self.sizeSets[ip] += self.sizeSets[jp]\n",
    "\n",
    "        # 若两树等高，任选一种方案，新树 rank +1\n",
    "        else:\n",
    "            self.parents[jp] = ip\n",
    "            self.sizeSets[ip] += self.sizeSets[jp]\n",
    "            self.ranks[ip] += 1\n",
    "\n",
    "    \n",
    "    def isSameSet(self, i: int, j: int) -> bool:\n",
    "        \"\"\"判断节点i和节点j是否属于同一集合\n",
    "           T: O(α(N) first O(N) then O(1)\n",
    "        \"\"\"\n",
    "        # path compression twice\n",
    "        return self.findSet(i) == self.findSet(j)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        UFA = UnionFind(n)\n",
    "        UFB = UnionFind(n)\n",
    "\n",
    "        # use common edge first\n",
    "        for type, u, v in edges:\n",
    "            if type == 3:\n",
    "                if UFA.unionSet(u-1, v-1):\n",
    "                    UFB.unionSet(u-1, v-1)\n",
    "                else:\n",
    "                    ans += 1\n",
    "        \n",
    "        # use exclusive edge next\n",
    "        for type, u, v in edges:\n",
    "            # Alice only edge\n",
    "            if (type == 1 and not UFA.unionSet(u-1, v-1)) or (type == 2 and not UFB.unionSet(u-1, v-1)):\n",
    "                ans += 1\n",
    "        \n",
    "        if UFA.numSets == UFB.numSets == 1:\n",
    "            return ans \n",
    "        \n",
    "        return -1 \n",
    "\n",
    "                    \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int, m: int=None) -> None:\n",
    "        \"\"\"\n",
    "        build m disjoint sets from n nodes\n",
    "        T: O(N)\n",
    "        \"\"\"\n",
    "        self.parents = list(range(n))   \n",
    "        self.ranks = [0] * n            \n",
    "        self.numSets = n                # number of disjoint sets\n",
    "\n",
    "\n",
    "    \n",
    "    def findSet(self, i: int) -> int:\n",
    "        \"\"\"return root of node i's set\n",
    "           T: amortized O(α(N))  effectively O(1)\n",
    "             first O(N) then O(1)\n",
    "           path-compression  \n",
    "           Recursion\n",
    "        \"\"\"\n",
    "        if self.parents[i] == i:\n",
    "            return i\n",
    "        else:\n",
    "            self.parents[i] = self.findSet(self.parents[i])\n",
    "            return self.parents[i]\n",
    "        \n",
    "    \n",
    "    def unionSet(self, i: int, j: int) -> None:\n",
    "        \"\"\"若节点i和节点j来自2个不同的互斥集合，将两个集合合并 \n",
    "           union by rank   矮树作为高树的子树\n",
    "           T: amortized O(α(N))  effectively O(1)\n",
    "             first O(N) then O(1)\n",
    "        \"\"\"\n",
    "        ip, jp = self.findSet(i), self.findSet(j)\n",
    "\n",
    "        # 若两个节点来自同一互斥集合，返回\n",
    "        if ip == jp:\n",
    "            return False \n",
    "\n",
    "        # 若A树矮，B树高，A树连到B树的根节点上，新树rank不变\n",
    "        if self.ranks[ip] < self.ranks[jp]:\n",
    "            self.parents[ip] = jp\n",
    "\n",
    "        # 若B树矮，A树高，B树连到A树的根节点上，新树rank不变\n",
    "        elif self.ranks[jp] < self.ranks[ip]:\n",
    "            self.parents[jp] = ip\n",
    "\n",
    "        # 若两树等高，任选一种方案，新树 rank +1\n",
    "        else:\n",
    "            self.parents[jp] = ip\n",
    "            self.ranks[ip] += 1\n",
    "\n",
    "        # 互斥集总数-1\n",
    "        self.numSets -= 1\n",
    "\n",
    "        return True\n",
    "    \n",
    "    def isSameSet(self, i: int, j: int) -> bool:\n",
    "        \"\"\"判断节点i和节点j是否属于同一集合\n",
    "           T: O(α(N) first O(N) then O(1)\n",
    "        \"\"\"\n",
    "        # path compression twice\n",
    "        return self.findSet(i) == self.findSet(j)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "        def compress_matrix(matrix: List[List[int]]) -> List[List[int]]:\n",
    "            rows, cols = len(matrix), len(matrix[0])\n",
    "            compressed_matrix = [[] for _ in range(rows)]\n",
    "            for row in range(rows):\n",
    "                for col in range(cols):\n",
    "                    if matrix[row][col]:\n",
    "                        compressed_matrix[row].append([matrix[row][col], col])\n",
    "            return compressed_matrix\n",
    "        \n",
    "        m = len(mat1)\n",
    "        k = len(mat1[0])\n",
    "        n = len(mat2[0])\n",
    "        \n",
    "        # 存储每个矩阵的非零值。\n",
    "        A = compress_matrix(mat1)\n",
    "        B = compress_matrix(mat2)\n",
    "        \n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        \n",
    "        for mat1_row in range(m):\n",
    "            #  迭代 mat1 的所有当前“行”非零元素。\n",
    "            for element1, mat1_col in A[mat1_row]:\n",
    "                # 将 mat2 中的所有非零元素相乘并相加\n",
    "                # 其中一行等于 mat1 中当前元素的 col。\n",
    "                for element2, mat2_col in B[mat1_col]:\n",
    "                    ans[mat1_row][mat2_col] += element1 * element2\n",
    "                    \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "        def compress_matrix(matrix):\n",
    "            n_rows, n_cols = len(matrix), len(matrix[0])\n",
    "            compressed_matrix = [[] for _ in range(n_rows)]\n",
    "            for row_index in range(n_rows):\n",
    "                for col_index in range(n_cols):\n",
    "                    if matrix[row_index][col_index]:\n",
    "                        compressed_matrix[row_index].append([matrix[row_index][col_index], col_index])\n",
    "            return compressed_matrix\n",
    "\n",
    "        A = compress_matrix(mat1)\n",
    "        B = compress_matrix(mat2)\n",
    "        m, n = len(mat1), len(mat2[0])\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "\n",
    "        for A_row_index in range(m):\n",
    "            for element_A, A_col_index in A[A_row_index]:\n",
    "                for element_B, B_col_index in B[A_col_index]:\n",
    "                    ans[A_row_index][B_col_index] += element_A * element_B\n",
    "                    \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        memo = {}\n",
    "        \n",
    "        # Helper function to compute compression length of continuous characters\n",
    "        def get_compressed_length(count):\n",
    "            if count == 1:\n",
    "                return 1\n",
    "            elif count < 10:\n",
    "                return 2\n",
    "            elif count < 100:\n",
    "                return 3\n",
    "            else:\n",
    "                return 4\n",
    "\n",
    "        # Recursive function\n",
    "        def dp(i, k):\n",
    "            # If we've exceeded allowable deletions, return a large value\n",
    "            if k < 0:\n",
    "                return float('inf')\n",
    "            \n",
    "            # If we've processed the entire string, return 0\n",
    "            if i >= n:\n",
    "                return 0\n",
    "            \n",
    "            if (i, k) in memo:\n",
    "                return memo[(i, k)]\n",
    "            \n",
    "            # Case 1: delete current character\n",
    "            ans = dp(i + 1, k - 1)\n",
    "            \n",
    "            # Case 2: keep current character and try different compression lengths\n",
    "            count = 0\n",
    "            diff_char_count = 0\n",
    "            j = i\n",
    "            while j < n and diff_char_count <= k:\n",
    "                if s[j] == s[i]:\n",
    "                    count += 1\n",
    "                else:\n",
    "                    diff_char_count += 1\n",
    "                ans = min(ans, get_compressed_length(count) + dp(j + 1, k - diff_char_count))\n",
    "                j += 1\n",
    "\n",
    "            memo[(i, k)] = ans\n",
    "            return ans\n",
    "        \n",
    "        return dp(0, k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compress(self, chars: List[str]) -> int:\n",
    "        i = 0\n",
    "        res =0\n",
    "        while i< len(chars):\n",
    "            group_length = 1\n",
    "            while (i + group_length < len(chars)) and chars[i + group_length] == chars[i]:\n",
    "                group_length += 1\n",
    "            chars[res] = chars[i]\n",
    "            res += 1\n",
    "            if group_length > 1:\n",
    "                str_rept = str(group_length)\n",
    "                chars[res:res+len(str_rept)] = list(str_rept)\n",
    "                res += len(str_rept)\n",
    "            i += group_length\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compress(self, chars):\n",
    "        \"\"\"\n",
    "        :type chars: List[str]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        length = len(chars)\n",
    "        if length <= 1:\n",
    "            return length\n",
    "        c_str = chars[0]\n",
    "        c_len, i, all_len = 1, 1, 0\n",
    "        while all_len < length:\n",
    "            while i < len(chars) and chars[i] == c_str:\n",
    "                c_len += 1\n",
    "                i += 1\n",
    "            all_len += c_len\n",
    "            if c_len > 1:\n",
    "                temp = []\n",
    "                for m in str(c_len):\n",
    "                    temp.append(m)\n",
    "                chars[i - c_len + 1:i] = temp\n",
    "                i -= c_len - len(str(c_len)) - 1\n",
    "            if i < len(chars):\n",
    "                c_str = chars[i]\n",
    "                c_len = 0\n",
    "        return len(chars)          "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compress(self, chars):\n",
    "        \"\"\"\n",
    "        :type chars: List[str]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        anchor = write = 0\n",
    "        for read, c in enumerate(chars):\n",
    "            if read + 1 == len(chars) or chars[read+1] != c:\n",
    "                chars[write] = chars[anchor]\n",
    "                write += 1\n",
    "                if read>anchor:\n",
    "                    for digit in str(read-anchor+1):\n",
    "                        chars[write] = digit\n",
    "                        write+=1\n",
    "                anchor = read+1\n",
    "                \n",
    "        return write"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compress(self, chars):\n",
    "        \"\"\"\n",
    "        :type chars: List[str]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        k = 1\n",
    "        res = 0\n",
    "        a = 0\n",
    "        for i in range(len(chars)):\n",
    "            if i >= len(chars)-1 or chars[i] != chars[i+1]:\n",
    "                if k != 1:\n",
    "                    chars[a] = chars[i]\n",
    "                    a += 1\n",
    "                    res += 1\n",
    "                    for e in str(k):\n",
    "                        chars[a] = e\n",
    "                        a += 1\n",
    "                        res += 1\n",
    "                    k = 1\n",
    "                else:\n",
    "                    chars[a] = chars[i]\n",
    "                    a += 1\n",
    "                    res += 1\n",
    "            else:\n",
    "                k += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compress(self, chars):\n",
    "        \"\"\"\n",
    "        :type chars: List[str]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        curr=''      #用额外的字符串保存经历过的字符和个数\n",
    "        count=1\n",
    "        l=len(chars)\n",
    "        if l==1:\n",
    "            return 1\n",
    "        for i in range(1,l):\n",
    "            if chars[i-1]==chars[i]:   \n",
    "                count+=1\n",
    "            else:\n",
    "                if count>1:\n",
    "                    curr+=chars[i-1]+str(count)\n",
    "                else:\n",
    "                    curr+=chars[i-1]\n",
    "                count=1\n",
    "        if count>1:       #最后一个字符\n",
    "            curr+=chars[i-1]+str(count)\n",
    "        else:\n",
    "            curr+=chars[i]\n",
    "        curr=list(curr)\n",
    "        chars[::]=curr[::]\n",
    "        return len(chars)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compress(self, chars):\n",
    "        \"\"\"\n",
    "        :type chars: List[str]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # if len(chars) == 1:\n",
    "        #     return 1\n",
    "        # charlist = []\n",
    "        # count = 1\n",
    "        # for i in range(len(chars)-1):\n",
    "        #     if chars[i+1] == chars [i]:\n",
    "        #         count += 1\n",
    "        #     else:\n",
    "        #         if count > 1:\n",
    "        #             charlist.append(chars[i])\n",
    "        #             charlist.extend(list(str(count)))\n",
    "        #             count = 1\n",
    "        #         else:\n",
    "        #             charlist.append(chars[i])\n",
    "        # if count > 1:\n",
    "        #     charlist.append(chars[-1])\n",
    "        #     charlist.extend(list(str(count)))\n",
    "        # else:\n",
    "        #     charlist.append(chars[-1])\n",
    "        # chars[::] = charlist[::]\n",
    "        # return len(chars)\n",
    "        \n",
    "        \n",
    "        index = 0\n",
    "        num = 1\n",
    "\n",
    "        for i in range(1, len(chars) + 1):\n",
    "            if i < len(chars) and chars[i] == chars[i - 1]:\n",
    "                num += 1\n",
    "            else:\n",
    "                chars[index] = chars[i - 1]\n",
    "                if num > 1:\n",
    "                    for m in str(num):\n",
    "                        index += 1\n",
    "                        chars[index] = m\n",
    "\n",
    "                index += 1\n",
    "\n",
    "                num = 1\n",
    "        print(chars)\n",
    "        return index\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compress(self, chars):\n",
    "        \"\"\"\n",
    "        :type chars: List[str]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        output=[]\n",
    "        if len(chars)<=1:\n",
    "            return 1\n",
    "        else:\n",
    "            for group,items in itertools.groupby(chars):\n",
    "                lenght=len(list(items))\n",
    "                print(lenght)\n",
    "                if lenght==1:\n",
    "                    output.append(group)\n",
    "                else:\n",
    "                    print(len(list(items)))\n",
    "                    output.append(group)\n",
    "                    number=list(str(lenght))\n",
    "                    for i in number:\n",
    "                        output.append(i)\n",
    "            chars[0:len(output)]=output\n",
    "            return len(output)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compress(self, chars):\n",
    "        \"\"\"\n",
    "        :type chars: List[str]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not chars:\n",
    "            return 0\n",
    "\n",
    "        if len(chars) == 1:\n",
    "            return 1\n",
    "\n",
    "        i = 0\n",
    "        while i < len(chars):\n",
    "            c = chars[i]\n",
    "            n = 1\n",
    "\n",
    "            while True:\n",
    "                if i + 1 == len(chars):\n",
    "                    if n > 1:\n",
    "                        for s in str(n):\n",
    "                            chars.append(s)\n",
    "                        # print(chars)\n",
    "                    return len(chars)\n",
    "\n",
    "                if chars[i + 1] == c:\n",
    "                    n += 1\n",
    "                    chars.pop(i + 1)\n",
    "                    continue\n",
    "\n",
    "                else:\n",
    "                    x = len(str(n))\n",
    "                    if n == 1:\n",
    "                        i += 1\n",
    "                    if n > 1:\n",
    "                        for s in str(n)[::-1]:\n",
    "                            chars.insert(i + 1, s)\n",
    "                        i += x + 1\n",
    "                    break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compress(self, chars):\n",
    "        \"\"\"\n",
    "        :type chars: List[str]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if len(chars)==1:\n",
    "            return 1\n",
    "        last_index=0\n",
    "        last_char=chars[0]\n",
    "        counter=0\n",
    "        for char in chars:\n",
    "            print(counter)\n",
    "            if char!=last_char:\n",
    "                if counter!=1:\n",
    "                    stack=[]\n",
    "                    while counter!=0:\n",
    "                        stack.append(counter%10)\n",
    "                        counter//=10\n",
    "                    while len(stack):\n",
    "                        last_index+=1\n",
    "                        chars[last_index]=str(stack.pop())\n",
    "                last_index+=1\n",
    "                chars[last_index]=char\n",
    "                counter=1\n",
    "                last_char=char\n",
    "            else:\n",
    "                counter+=1\n",
    "        if counter!=1:\n",
    "            stack=[]\n",
    "            while counter!=0:\n",
    "                stack.append(counter%10)\n",
    "                counter//=10\n",
    "            while len(stack):\n",
    "                last_index+=1\n",
    "                chars[last_index]=str(stack.pop())\n",
    "        while len(chars)!=last_index+1:\n",
    "            chars.pop()\n",
    "        return last_index+1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def compress(self, chars):\n",
    "        anchor = write = 0\n",
    "        for read, c in enumerate(chars):\n",
    "            if read + 1 == len(chars) or chars[read + 1] != c:\n",
    "                chars[write] = chars[anchor]\n",
    "                write += 1\n",
    "                if read > anchor:\n",
    "                    for digit in str(read - anchor + 1):\n",
    "                        chars[write] = digit\n",
    "                        write += 1\n",
    "                anchor = read + 1\n",
    "        return write\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compress(self, chars: List[str]) -> int:\n",
    "        res=1\n",
    "        i,j=0,1\n",
    "        chars.append('')\n",
    "        while j<len(chars):\n",
    "            if chars[j]!=chars[i]:\n",
    "                count=j-i\n",
    "                if count>1:\n",
    "                    for s in str(count):\n",
    "                        chars[res]=s\n",
    "                        res+=1\n",
    "                chars[res]=chars[j]\n",
    "                i=j\n",
    "                res+=1\n",
    "            j+=1\n",
    "        return res-1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compress(self, chars: List[str]) -> int:\n",
    "\n",
    "        # count = 1\n",
    "        # for i in range(len(chars))[::-1]:\n",
    "        #     if chars[i] == chars[i-1]:\n",
    "        #         count += 1\n",
    "        #         chars.pop()\n",
    "        #         print(chars)\n",
    "        #     else:\n",
    "        #         chars.append(str(count))\n",
    "        #         count = 1\n",
    "\n",
    "        # chars = [char for char in (chars)]\n",
    "\n",
    "        # return chars\n",
    "\n",
    "        anchor = write = 0\n",
    "        for read, c in enumerate(chars):\n",
    "            if read + 1 == len(chars) or chars[read + 1] != c:\n",
    "                chars[write] = chars[anchor]\n",
    "                write += 1\n",
    "                if read > anchor:\n",
    "                    for digit in str(read - anchor + 1):\n",
    "                        chars[write] = digit\n",
    "                        write += 1\n",
    "                anchor = read + 1\n",
    "        return write\n",
    "\n",
    "        # 作者：LeetCode\n",
    "        # 链接：https://leetcode-cn.com/problems/string-compression/solution/ya-suo-zi-fu-chuan-by-leetcode/\n",
    "        # 来源：力扣（LeetCode）\n",
    "        # 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compress(self, chars: List[str]) -> int:\n",
    "\n",
    "        cnt = 1\n",
    "        res = 0\n",
    "\n",
    "        for i in range(1, len(chars)):\n",
    "            if chars[res] != chars[i]:\n",
    "                if cnt != 1:\n",
    "                    for k in list(str(cnt)):\n",
    "                        res += 1\n",
    "                        chars[res] = k\n",
    "                res += 1\n",
    "                chars[res] = chars[i]\n",
    "                cnt = 1\n",
    "            else:\n",
    "                cnt += 1\n",
    "\n",
    "        if cnt != 1:\n",
    "            for k in list(str(cnt)):\n",
    "                res += 1\n",
    "                chars[res] = k\n",
    "\n",
    "        return res + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compress(self, chars):\n",
    "        anchor = write = 0\n",
    "        for read, c in enumerate(chars):\n",
    "            if read + 1 == len(chars) or chars[read + 1] != c:\n",
    "                chars[write] = chars[anchor]\n",
    "                write += 1\n",
    "                if read > anchor:\n",
    "                    for digit in str(read - anchor + 1):\n",
    "                        chars[write] = digit\n",
    "                        write += 1\n",
    "                anchor = read + 1\n",
    "            if read+1==len(chars):\n",
    "                chars = chars[:write]\n",
    "\n",
    "        return len(chars)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def compress(self, chars):\n",
    "        anchor = write = 0\n",
    "        for read, c in enumerate(chars):\n",
    "            if read + 1 == len(chars) or chars[read + 1] != c:\n",
    "                chars[write] = chars[anchor]\n",
    "                write += 1\n",
    "                if read > anchor:\n",
    "                    for digit in str(read - anchor + 1):\n",
    "                        chars[write] = digit\n",
    "                        write += 1\n",
    "                anchor = read + 1\n",
    "        return write\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compress(self, chars: List[str]) -> int:\n",
    "        if not chars:\n",
    "            return 0\n",
    "        index = 0  \n",
    "        lens = len(chars)\n",
    "        i = 0  # 首字母指针\n",
    "        while i < lens:\n",
    "            j = i + 1  # 最后同字母指针\n",
    "            while j < lens and chars[j] == chars[i]:\n",
    "                j += 1\n",
    "            if j - i > 1:  \n",
    "                chars[index] = chars[i]\n",
    "                index += 1\n",
    "                strs = str(j - i)\n",
    "                for s in strs:\n",
    "                    chars[index] = s\n",
    "                    index += 1\n",
    "            else: \n",
    "                chars[index] = chars[i]\n",
    "                index += 1\n",
    "            i = j\n",
    "        return index\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compress(self, chars: List[str]) -> int:\n",
    "        result = \"\"\n",
    "        idx = 0\n",
    "        while idx < len(chars):\n",
    "            curChar = chars[idx]\n",
    "            curLen = 0\n",
    "            while idx < len(chars) and chars[idx] == curChar:\n",
    "                idx += 1\n",
    "                curLen += 1\n",
    "            if curLen > 1:\n",
    "                result += curChar + str(curLen)\n",
    "            else:\n",
    "                result += curChar\n",
    "        chars[:len(result)] = result\n",
    "        return len(result)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compress(self, chars: List[str]) -> int:\n",
    "        l=0\n",
    "        r=0\n",
    "        w=0\n",
    "        # print(chars)\n",
    "        # print(len(chars))\n",
    "        for i in range(len(chars)):\n",
    "            print(i)\n",
    "            if i+1==len(chars) or chars[i+1]!=chars[i]:           \n",
    "                # print(chars)\n",
    "                # print('w',w)\n",
    "                chars[w] = chars[l]\n",
    "                w+=1\n",
    "                if i > l:\n",
    "                    for digit in str(i - l + 1):\n",
    "                        chars[w] = digit\n",
    "                        w += 1\n",
    "                l=i+1\n",
    "        return w\n",
    "        # anchor = write = 0\n",
    "        # for read, c in enumerate(chars):\n",
    "        #     if read + 1 == len(chars) or chars[read + 1] != c:\n",
    "        #         chars[write] = chars[anchor]\n",
    "        #         write += 1\n",
    "        #         if read > anchor:\n",
    "        #             for digit in str(read - anchor + 1):\n",
    "        #                 chars[write] = digit\n",
    "        #                 write += 1\n",
    "        #         anchor = read + 1\n",
    "        # return write"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compress(self, chars: List[str]) -> int:\n",
    "        '''\n",
    "        记录当前字母的数字数，这个不难\n",
    "        难的是怎么原地操作。。。\n",
    "        图省事我肯定直接在中间remove了\n",
    "        '''\n",
    "        '''\n",
    "        本来想用s.count，但是遇到[\"a\",\"a\",\"a\",\"b\",\"b\",\"a\",\"a\"]，直接歇菜了了\n",
    "        '''\n",
    "        \n",
    "        '''\n",
    "        双指针，一个往前读，一个在原地写。写比读慢。读到头，写跟着停止。此时写到的位置，就是新数组的长度了\n",
    "        '''\n",
    "        if chars==[]:\n",
    "            return 0\n",
    "        w=0 #每次前进“写的内容”的距离\n",
    "        cur=chars[0]\n",
    "        cnt=1\n",
    "        for r,c in enumerate(chars[1:]):\n",
    "            print(cur,c,cnt,w,chars[w])\n",
    "            if cur!=c:\n",
    "                if cnt==1:\n",
    "                    chars[w]=cur\n",
    "                    w+=1 #写一个cur，前进1\n",
    "                else:\n",
    "                    st=[cur]+list(str(cnt)) #写一个c+num的距离\n",
    "                    chars[w:w+len(st)]=st\n",
    "                    w+=len(st)\n",
    "                cur=c\n",
    "                cnt=1\n",
    "            else:\n",
    "                cnt+=1\n",
    "        if cnt>1:\n",
    "            st=[cur]+list(str(cnt)) #写一个c+num的距离\n",
    "            chars[w:w+len(st)]=st\n",
    "            w+=len(st)\n",
    "        else:\n",
    "            chars[w]=cur\n",
    "            w+=1\n",
    "        return w\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compress(self, chars: List[str]) -> int:\n",
    "        i,j=0,0\n",
    "        n=len(chars)\n",
    "        while j<n:\n",
    "            cnt=0\n",
    "            s=chars[j]\n",
    "            while j<n and chars[j]==s:\n",
    "                j+=1\n",
    "                cnt+=1\n",
    "            chars[i]=s\n",
    "            i+=1\n",
    "            if cnt>1:\n",
    "                for m in list(str(cnt)):\n",
    "                    chars[i]=m\n",
    "                    i+=1\n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "import math\n",
    "from typing import *\n",
    "from functools import lru_cache\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def compress(self, chars: List[str]) -> int:\n",
    "        i,j=0,0\n",
    "        ans=0\n",
    "        k=0\n",
    "        while j<len(chars):\n",
    "            while j<len(chars) and  chars[j]==chars[i]:\n",
    "                j+=1\n",
    "            cnt=j-i\n",
    "            s=chars[i]+(str(cnt) if cnt!=1 else \"\")\n",
    "            for si in s:\n",
    "                chars[k]=si\n",
    "                k+=1\n",
    "            ans+=1+(len(str(cnt)) if cnt!=1 else 0)\n",
    "            i=j\n",
    "        chars=chars[:k]\n",
    "        # print(chars)\n",
    "        return ans\n",
    "s=Solution()\n",
    "print(s.compress(chars=[\"a\", \"a\", \"b\", \"b\", \"c\", \"c\", \"c\"]))\n",
    "print(s.compress(chars=[\"a\"]))\n",
    "print(s.compress(chars=[\"a\",\"b\",\"b\",\"b\",\"b\",\"b\",\"b\",\"b\",\"b\",\"b\",\"b\",\"b\",\"b\"]))\n",
    "\n",
    "\n",
    "s=Solution()\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compress(self, chars: List[str]) -> int:\n",
    "        length = len(chars)\n",
    "        if length == 1:\n",
    "            return length\n",
    "        i = 0\n",
    "        while i < length:\n",
    "            count = 1\n",
    "            j = i +1\n",
    "            while j < length and chars[i] == chars[j]:\n",
    "                chars[j] =None\n",
    "                count +=1\n",
    "                j +=1\n",
    "            # print(chars[i],count)\n",
    "            if count ==1:\n",
    "                i +=1\n",
    "            elif 1 < count < 10:\n",
    "                chars[i+1] = str(count)\n",
    "            else:\n",
    "                for x in range(len(str(count))):\n",
    "                    chars[i+1+x] = str(count)[x]\n",
    "            i = j \n",
    "        # print(chars)\n",
    "        i= 0\n",
    "        while i < len(chars):\n",
    "            if chars[i] == None:\n",
    "                chars.pop(i)\n",
    "                i -=1\n",
    "            i +=1\n",
    "        return len(chars)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compress(self, chars: List[str]) -> int:\n",
    "        pre = '_'\n",
    "        cnt = 0\n",
    "        pos = 0\n",
    "        for idx,c in enumerate(chars):\n",
    "            if c == pre:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                scnt = str(cnt)\n",
    "                if cnt != 0:\n",
    "                    chars[pos] = pre\n",
    "                    pos += 1\n",
    "                if cnt > 1:\n",
    "                    l = len(scnt)\n",
    "                    for i in range(l):\n",
    "                        chars[pos] = scnt[i]\n",
    "                        pos+=1\n",
    "                cnt =  1\n",
    "                pre = c\n",
    "        scnt = str(cnt)\n",
    "        chars[pos] = pre\n",
    "        pos += 1\n",
    "        if cnt > 1:\n",
    "            l = len(scnt)\n",
    "            for i in range(l):\n",
    "                chars[pos] = scnt[i]\n",
    "                pos+=1\n",
    "        return pos\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compress(self, chars: List[str]) -> int:\n",
    "        # new_str = []\n",
    "        # current = chars[0]\n",
    "        # num = 1\n",
    "        # for i in range(len(chars) - 1):\n",
    "        #     if chars[i+1] == current:\n",
    "        #         num += 1\n",
    "        #     else:\n",
    "        #         new_str.append(current)\n",
    "        #         str_num = str(num)\n",
    "        #         for j in range(len(str_num)):\n",
    "        #             new_str.append(str_num[j])\n",
    "        #         num = 1\n",
    "        #         current = chars[i+1]\n",
    "        # new_str.append(current)\n",
    "        # str_num = str(num)\n",
    "        # for j in range(len(str_num)):\n",
    "        #     new_str.append(str_num[j])\n",
    "\n",
    "        # print(new_str)\n",
    "\n",
    "        # return len(new_str)\n",
    "\n",
    "        current = chars[0]\n",
    "        num = 1\n",
    "        idx = 1\n",
    "        while True:\n",
    "            if idx >= len(chars):\n",
    "                str_num = str(num)\n",
    "                if num > 1:\n",
    "                    for j in range(len(str_num)):\n",
    "                        chars.insert(idx+j, str_num[j])\n",
    "                idx = idx+len(str_num)\n",
    "                break\n",
    "            if chars[idx] == current:\n",
    "                num+=1\n",
    "                del(chars[idx])\n",
    "            else:\n",
    "                str_num = str(num)\n",
    "                if num > 1:\n",
    "                    for j in range(len(str_num)):\n",
    "                        chars.insert(idx+j, str_num[j])\n",
    "                    idx = idx+len(str_num)\n",
    "                print(current)\n",
    "                print(str_num)\n",
    "                print(len(str_num))\n",
    "                current = chars[idx]\n",
    "                idx = idx + 1\n",
    "                num = 1\n",
    "        return len(chars)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compress(self, chars: List[str]) -> int:\n",
    "        ans = [chars[0]]\n",
    "        L = len(chars)\n",
    "        tmp = 1\n",
    "        for i in range(1,L):\n",
    "            print(i,chars[i],ans,tmp)\n",
    "\n",
    "            if chars[i] == chars[i-1]:\n",
    "                tmp += 1\n",
    "            else:\n",
    "                # print('z')\n",
    "                if tmp == 1:\n",
    "                    # print('x')\n",
    "                    ans.append(chars[i])\n",
    "                else:\n",
    "                    # print('y')\n",
    "\n",
    "                    ans.extend([c for c in str(tmp)])\n",
    "                    ans.append(chars[i])\n",
    "                    tmp = 1\n",
    "        if tmp > 1:\n",
    "            ans.extend([c for c in str(tmp)])\n",
    "        for i in range(len(ans)):\n",
    "            chars[i] = ans[i]\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#22大数据1班 蔡沛璇、张子桐、邓晓靖小组 4.5压缩字符串\n",
    "class Solution:\n",
    "    def compress(self, chars: List[str]) -> int:\n",
    "        i,k=0,0\n",
    "        while i<len(chars):\n",
    "            chars[k]=chars[i]\n",
    "            k+=1\n",
    "            cnt=1\n",
    "            i+=1\n",
    "            while i<len(chars) and chars[i]==chars[k-1]:\n",
    "                i,cnt=i+1,cnt+1\n",
    "            if cnt>1:\n",
    "                tmp=list(str(cnt))\n",
    "                for j in range(len(tmp)):\n",
    "                    chars[k]=tmp[j]\n",
    "                    k+=1\n",
    "        return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compress(self, chars: List[str]) -> int:\n",
    "        if not chars:\n",
    "            return \"\"\n",
    "\n",
    "        write_index = 0  # 写指针\n",
    "        read_index = 0   # 读指针\n",
    "\n",
    "        while read_index < len(chars):\n",
    "            current_char = chars[read_index]\n",
    "            count = 0\n",
    "\n",
    "            # 计算当前字符的连续重复次数\n",
    "            while read_index < len(chars) and chars[read_index] == current_char:\n",
    "                read_index += 1\n",
    "                count += 1\n",
    "\n",
    "            # 写入字符\n",
    "            chars[write_index] = current_char\n",
    "            write_index += 1\n",
    "\n",
    "            # 如果当前字符有重复，则写入重复次数\n",
    "            if count > 1:\n",
    "                for digit in str(count):\n",
    "                    chars[write_index] = digit\n",
    "                    write_index += 1\n",
    "                    \n",
    "        return write_index"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compress(self, chars: List[str]) -> int:\n",
    "        point = left = 0\n",
    "        chars.append(' ')\n",
    "        for right, char in enumerate(chars):\n",
    "            if char != chars[left]:\n",
    "                chars[point] = chars[left]\n",
    "                point += 1\n",
    "                distance = right - left\n",
    "                if distance > 1:\n",
    "                    for i in str(distance):\n",
    "                        chars[point] = i\n",
    "                        point += 1\n",
    "                left = right\n",
    "        return point"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
